package leetcode

type NumArray struct {
	segmentTree []int
	length      int
}

func buildTree(numArray *NumArray, pos, left, right int, nums []int) {
	if left == right {
		numArray.segmentTree[pos] = nums[left]
		return
	}
	middle := (left + right) >> 1
	left_pos := 2*pos + 1
	right_pos := left_pos + 1
	buildTree(numArray, left_pos, left, middle, nums)
	buildTree(numArray, right_pos, middle+1, right, nums)
	numArray.segmentTree[pos] = numArray.segmentTree[left_pos] + numArray.segmentTree[right_pos]
}

func (this *NumArray) update(pos, left, right int, index int, val int) {
	if left == right {
		this.segmentTree[pos] = val
		return
	}

	middle := (left + right) >> 1
	left_pos := 2*pos + 1
	right_pos := left_pos + 1
	if index <= middle {
		this.update(left_pos, left, middle, index, val)
	} else {
		this.update(right_pos, middle+1, right, index, val)
	}
	this.segmentTree[pos] = this.segmentTree[left_pos] + this.segmentTree[right_pos]
}

func (this *NumArray) sumRange(pos, my_left, my_right int, left int, right int) int {
	if left <= my_left && my_right <= right {
		return this.segmentTree[pos]
	}

	middle := (my_left + my_right) >> 1
	left_pos := 2*pos + 1
	right_pos := left_pos + 1
	res := 0

	if left <= middle {
		res += this.sumRange(left_pos, my_left, middle, left, right)
	}
	if right > middle {
		res += this.sumRange(right_pos, middle+1, my_right, left, right)
	}
	return res
}

func Constructor(nums []int) NumArray {
	length := len(nums)
	res := NumArray{segmentTree: make([]int, 4*length), length: length}
	buildTree(&res, 0, 0, length-1, nums)
	return res
}

func (this *NumArray) Update(index int, val int) {
	this.update(0, 0, this.length-1, index, val)
}

func (this *NumArray) SumRange(left int, right int) int {
	return this.sumRange(0, 0, this.length-1, left, right)
}
